package mashibing.freshman.class05;

/**
 * 位运算实现加减乘除
 * 不用加减乘除模，只用位运算
 */
// 测试链接：https://leetcode.com/problems/divide-two-integers
public class Code03_BitAddMinusMultiDiv {
	// 加法【不能用+】
	public static int add(int a, int b) {
		int sum = a;
		while (b != 0) {
			sum = a ^ b;//异或【无进位相加】 --> sum
			b = (a & b) << 1;//进位信息 --> b-->b'
			a = sum;// a--> a'
		}
		return sum;
	}

	// 不能出现- 或+ ：
	// 求负数 = ~n+1
	public static int negNum(int n) {
		// 相反数 + 1
		return add(~n, 1);
	}
	// -b = ~b + 1
	// 减 a-b = a + (~b+1),不能出现- 或+
	public static int minus(int a, int b) {
		return add(a, negNum(b));
	}
	// 乘法，支持正负
	public static int multi(int a, int b) {
		int res = 0;
		while (b != 0) {
			if ((b & 1) != 0) {
				res = add(res, a);
			}
			a <<= 1;// a左移1位
			b >>>= 1;// b不带符号右移1位
		}
		return res;
	}

	// 是否为负数，负数：true
	public static boolean isNeg(int n) {
		return n < 0;
	}
	// 除 /
	public static int div(int a, int b) {
		int x = isNeg(a) ? negNum(a) : a;// 如果负数，则取反+1
		int y = isNeg(b) ? negNum(b) : b;
		int res = 0;
		// 31位是符号位 ， 0-30
		for (int i = 30; i >= 0; i = minus(i, 1)) {
			if ((x >> i) >= y) {// x右移i位，等同于y左移i位
				res |= (1 << i);
				x = minus(x, y << i);
			}
		}
		// ^【异或】可以用 != 代替
		return isNeg(a) ^ isNeg(b) ? negNum(res) : res;// 同正，同负，不变；一正一负，需要取反+1；看是否需要补符号
	}

	// 系统最小值无法转绝对值问题解决
	public static int divide(int a, int b) {
		// 1）a是系统最小，b是系统最小
		if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
			return 1;
		} else if (b == Integer.MIN_VALUE) {// 2）a不是系统最小，b是系统最小
			return 0;// 向上取整
		} else if (a == Integer.MIN_VALUE) {// 3）a是系统最小，b不是系统最小
			if (b == negNum(1)) {// Leetcode约定 最小值/-1 = 最大值 ； 理论上 = 最大值+1
				return Integer.MAX_VALUE;
			} else {
				// (a+1)/b = c
				// a-(b*c) = d
				// d/b = e
				// result = c + e
				int c = div(add(a, 1), b);
				return add(c, div(minus(a, multi(c, b)), b));
			}
		} else {// 4）a不是系统最小，b不是系统最小
			return div(a, b);// 就是上面的解法
		}
	}

}
